package xyf.p08.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * ClassName: P0077_Combine
 * Description:
 * Author: xyf
 * Date: 9/8/22 9:48 AM
 * Version: 1.0
 **/
public class P0077_Combine
{
    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k)
    {
        dfs(n, 0, k, new ArrayList<>());
        return res;
    }

    private void dfs(int n, int curIndex, int k, List<Integer> path)
    {
        if (path.size() == k)
        {
            res.add(new ArrayList<>(path));
            return;
        }

        if (curIndex == n)
        {
            return;
        }

        path.add(curIndex + 1);
        dfs(n, curIndex + 1, k, path);
        path.remove(path.size() - 1);
        dfs(n, curIndex + 1, k, path);
    }
}